package com.peng.leetcode.list;

import java.util.Deque;
import java.util.LinkedList;

/**
 * ReverseList
 *
 * @author: lupeng6
 * @create: 2020/12/31 11:18
 */
public class ReverseList {

    public static void main(String[] args) {
        ListNode head = BuildListNode.tailInsert(1, 2, 3, 4, 5);
//        ListNode listNode = reverseByStack(head);
        ListNode listNode = reverseByIterate(head);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    /**
     * 通过栈的方式 反转链表
     *
     * @author lupeng6
     * @date 2020/12/31 11:28
     */
    public static ListNode reverseByStack(ListNode head) {
        if (head == null) {
            return null;
        }
        Deque<ListNode> deque = new LinkedList<>();
        ListNode dummy = head;
        while (dummy != null) {
            deque.offer(dummy);
            dummy = dummy.next;
        }
        ListNode currentNode = deque.pollLast();
        ListNode newHead = currentNode;
        while (!deque.isEmpty()) {
            currentNode.next = deque.pollLast();
            currentNode = currentNode.next;
        }
        currentNode.next = null;
        return newHead;
    }

    /**
     * 通过迭代的方式反转数组
     *
     * @author lupeng6
     * @date 2020/12/31 11:29
     */
    public static ListNode reverseByIterate(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }
}
